// Problem 225: Tribonacci non-divisors
// The sequence 1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201 …
// is defined by T1 = T2 = T3 = 1 and Tn = Tn-1 + Tn-2 + Tn-3.
// It can be shown that 27 does not divide any terms of this sequence. In fact, 27 is the first odd number with this property.
// Find the 124th odd number that does not divide any terms of the above sequence.

package main

import (
	"fmt"
	"math/big"
	"projecteuler/euler"
	"strconv"
)

func binomial(n, k int) *big.Int {
	ans := big.NewInt(1)
	bigN := big.NewInt(int64(1))
	for i := 0; i < k; i++ {
		bigN.SetInt64(int64(n - i))
		ans.Mul(ans, bigN)
	}
	ans.Div(ans, euler.Factorial(int64(k)))
	return ans
}

func p203() {
	x := []*big.Int{}
	x = append(x, big.NewInt(4), big.NewInt(9), big.NewInt(25), big.NewInt(49))
	zero := big.NewInt(0)
	var coinff map[string]int = make(map[string]int)
	for n := 1; n <= 50; n++ {
		stop := (n / 2)
		for k := 1; k <= stop; k++ {
			nk := binomial(n, k)
			flag := true
			for _, v := range x {
				temp := big.NewInt(1)
				if temp.Mod(nk, v).Cmp(zero) == 0 {
					flag = false
					break
				}
			}
			if flag {
				coinff[nk.String()] = 1
			}
		}
	}
	var sum int = 1
	for v := range coinff {
		i, _ := strconv.Atoi(v)
		sum += i
	}
	fmt.Println("Problem 203:", sum)
}
